/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q2497.java
 * @Author : WangRuoyu
 * @Date 2022/12/24 18:05
 */

package leetcode;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Q2497 {
    public int maxStarSum(int[] vals, int[][] edges, int k) {
        int res = -100001;

        int[][] twoEdges = new int[2 * edges.length][2];

        for (int i = 0; i < edges.length; i++) {
            twoEdges[i] = edges[i];
            twoEdges[i + edges.length][0] = edges[i][1];
            twoEdges[i + edges.length][1] = edges[i][0];
        }

        Arrays.sort(twoEdges, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    //若a[0] b[0]值相同则比较a[1] b[1]，按升序
                    return a[1] - b[1];
                } else {
                    return a[0] - b[0];
                }
            }
        });

        int index = 0;

        for (int i = 0; i < vals.length; i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = index; j < twoEdges.length; j++) {
                if (twoEdges[j][0] != i) {
                    index = j;
                    break;
                } else {
                    tmp.add(vals[twoEdges[j][1]]);
                }
            }
            if (tmp.size() <= k) {
                int p = vals[i];
                for (Integer x : tmp) {
                    if (x > 0) {
                        p += x;
                    }
                }
                res = Math.max(res, p);
            } else {
                int p = vals[i];
                tmp.sort(Comparator.naturalOrder());
                for (int j = tmp.size() - 1; j >= tmp.size() - k; j--) {
                    if (tmp.get(j) > 0) {
                        p += tmp.get(j);
                    }
                }
                res = Math.max(res, p);
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Q2497 sl = new Q2497();
//        int[] vals = {1, 2, 3, 4, 10, -10, -20};
//        int[][] edges = {{0, 1}, {1, 2}, {1, 3}, {3, 4}, {3, 5}, {3, 6}};
//        int k = 2;

        int[] vals = {0, -36, 4, 35, 27, -13};
        int[][] edges = {{5, 3}, {4, 3}, {0, 4}, {2, 4}, {0, 2}};
        int k = 1;

        System.out.println(sl.maxStarSum(vals, edges, k));
    }
}
